|
In numerical linear algebra, the QR algorithm is an eigenvalue algorithm: that is, a procedure to calculate the eigenvalues and eigenvectors of a matrix. The QR transformation was developed in the late 1950s by John G.F. Francis (England) and by Vera N. Kublanovskaya (USSR), working independently.〔 J.G.F. Francis, "The QR Transformation, I", ''The Computer Journal'', vol. 4, no. 3, pages 265-271 (1961, received Oct 1959) (online at oxfordjournals.org ); J.G.F. Francis, "The QR Transformation, II" ''The Computer Journal'', vol. 4, no. 4, pages 332-345 (1962) (online at oxfordjournals.org ). Vera N. Kublanovskaya, "On some algorithms for the solution of the complete eigenvalue problem," ''USSR Computational Mathematics and Mathematical Physics'', vol. 1, no. 3, pages 637–657 (1963, received Feb 1961). Also published in: ''Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki'', vol.1, no. 4, pages 555–570 (1961).〕 The basic idea is to perform a QR decomposition, writing the matrix as a product of an orthogonal matrix and an upper triangular matrix, multiply the factors in the reverse order, and iterate. ==The practical QR algorithm== Formally, let ''A'' be a real matrix of which we want to compute the eigenvalues, and let ''A''0:=''A''. At the ''k''-th step (starting with ''k'' = 0), we compute the QR decomposition ''A''''k''=''Q''''k''''R''''k'' where ''Q''''k'' is an orthogonal matrix (i.e., ''Q''''T'' = ''Q''−1) and ''R''''k'' is an upper triangular matrix. We then form ''A''''k''+1 = ''R''''k''''Q''''k''. Note that : so all the ''A''''k'' are similar and hence they have the same eigenvalues. The algorithm is numerically stable because it proceeds by ''orthogonal'' similarity transforms. Under certain conditions,〔Golub, G. H. and Van Loan, C. F.: Matrix Computations, 3rd ed., Johns Hopkins University Press, Baltimore, 1996, ISBN 0-8018-5414-8.〕 the matrices ''A''''k'' converge to a triangular matrix, the Schur form of ''A''. The eigenvalues of a triangular matrix are listed on the diagonal, and the eigenvalue problem is solved. In testing for convergence it is impractical to require exact zeros, but the Gershgorin circle theorem provides a bound on the error. In this crude form the iterations are relatively expensive. This can be mitigated by first bringing the matrix ''A'' to upper Hessenberg form (which costs arithmetic operations using a technique based on Householder reduction), with a finite sequence of orthogonal similarity transforms, somewhat like a two-sided QR decomposition.〔James W. Demmel, ''Applied Numerical Linear Algebra'' (SIAM, 1997).〕〔Lloyd N. Trefethen and David Bau, ''Numerical Linear Algebra'' (SIAM, 1997).〕 (For QR decomposition, the Householder reflectors are multiplied only on the left, but for the Hessenberg case they are multiplied on both left and right.) Determining the QR decomposition of an upper Hessenberg matrix costs arithmetic operations. Moreover, because the Hessenberg form is already nearly upper-triangular (it has just one nonzero entry below each diagonal), using it as a starting point reduces the number of steps required for convergence of the QR algorithm. If the original matrix is symmetric, then the upper Hessenberg matrix is also symmetric and thus tridiagonal, and so are all the ''A''''k''. This procedure costs arithmetic operations using a technique based on Householder reduction.〔〔 Determining the QR decomposition of a symmetric tridiagonal matrix costs operations.〔James M. Ortega and Henry F. Kaiser, "The ''LLT'' and ''QR'' methods for symmetric tridiagonal matrices," ''The Computer Journal'' 6 (1), 99–101 (1963).〕 The rate of convergence depends on the separation between eigenvalues, so a practical algorithm will use shifts, either explicit or implicit, to increase separation and accelerate convergence. A typical symmetric QR algorithm isolates each eigenvalue (then reduces the size of the matrix) with only one or two iterations, making it efficient as well as robust. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「QR algorithm」の詳細全文を読む スポンサード リンク
|